A standard matched FIR (Finite Impulse Response) filter is shown below in FIG. 1 and given by the equation:
      y          k      +              (                  N          -          1                )              =            ∑              n        =        0                    N        -        1              ⁢                  h        n            ⁢              r                  k          +          n                    where h represents the filter coefficients, r represents the data to be filtered, and N is the length of the filter. In FIG. 1, the z−1 symbol represents a unit delay operator, the X symbol represents a multiplier function, and the + symbol represents an adder function. Each data sample in the filter is multiplied by a tap coefficient and these products are summed to create a single output every time data is shifted in. In one realization of a complex multiplication, three FIR filters are needed to perform the four multiplications (using sums and differences). That is, three of the filters in FIG. 1 are needed in parallel.
The direct form FIR filter shown in FIG. 1 can be used as a matched filter for signal detection when the frequency of the received signal is known. In this case, the time of arrival of the signal is unknown (as well as the signal phase, typically). However, there are many applications (e.g., radar, satellite communications, etc.) where the frequency of received signal is unknown due to a Doppler frequency shift. Simply using one matched filter in these applications would result in a processing loss. To avoid this loss, a search for the signal must occur in time and frequency. This is called an ambiguity function. A standard ambiguity function equation is:
      χ    ⁡          (              τ        ,        f            )        =            ∫                        -          T                /        2                    T        /        2              ⁢                  r        ⁡                  (          t          )                    ⁢      s      *              (                  t          -          τ                )            ⁢              exp        ⁡                  (                                    -              j2π                        ⁢                                                  ⁢            ft                    )                    ⁢                          ⁢              ⅆ        t            where r is the received data, s is the signal that is being searched for, “*” denotes the complex conjugate, τ is the delay of the signal in the received data, f is the frequency shift of the signal in the received data, and T is the length of the received data.
The ambiguity function can be implemented in a number of ways. One standard implementation is to use a parallel bank of matched filters. The coefficients of each matched filter (i.e., the samples of the reference signal) are shifted in frequency from the coefficients of the other matched filters to perform detection at a specific frequency. In this implementation, the frequency shift between the coefficients of the different filters may be arbitrary, but is usually a compromise between processing loss and how many filters can be realized.
Another standard way of implementing an ambiguity function is to perform block processing using Fast Fourier Transforms (FFTs). This is also called the frequency-domain ambiguity function. In this method, a 2N-pt FFT of the reference signal is computed, where N is the length of the reference signal in samples. A matrix with circularly shifted versions of the reference FFT in each column is then generated. This sample shift in the frequency domain corresponds to a frequency shift in the time domain. Each sample shift corresponds to a frequency shift of 1/(2N·dt) Hz, where dt is the sample period. A block of data (often the length of the signal of interest) is captured and a 2N-pt FFT is performed. This FFT is multiplied point-by-point against the columns of the matrix and then the inverse FFT of each column is computed. The result is a matrix of the cross-correlations of the data against frequency-shifted versions of the reference signal. A new block of data is typically processed for every N input samples (i.e., not processed every sample).
A third implementation is called the time-domain ambiguity function. The data is shifted into a FIR filter and each data sample is multiplied by a filter coefficient. The FFT of the ensemble of these N products is then computed, which performs the frequency search. This may be repeated as often as every sample.
These three implementations are all essentially equivalent. The problem with these, and most, ambiguity function implementations is that they are resource-intensive. They require a significant amount of space in hardware, many computations, or both. In the matched filter bank, a filter is needed for every frequency of interest. Each filter has N taps, where N is the length of the signal, and every tap has a multiplier and an accumulator. In the frequency-domain approach an FFT twice the length of the reference, all the point-by-point multiplications, and an inverse FFT for each frequency of interest must be computed. In the time-domain approach, a FFT the length of the reference must be computed as often as every sample.
Another matched filter design modified to minimize frequency loss, such as described in U.S. Pat. No. 6,366,626, is specific to broadband, spread spectrum signals. It required a number of phase rotation-signal combiner stages and these each produced outputs associated with a number of frequency bins. Also, quantization of the phases for the combiner stages was necessary. Further, it lacked a means for accurately determining how many sub-filters were necessary for the frequency shift expected.